package com.s7.search;

import java.util.Arrays;

/**
 * 有序的循环数组中使用二分查找
 */
public class BsearchInLoopArray {

	public static void main(String[] args) {
		int[] array = { 4, 5, 6, 1, 2, 3};
		System.out.println("array = " + Arrays.toString(array));
		System.out.println("array = " + search(array, 1));
		System.out.println("array = " + search(array, 2));
		System.out.println("array = " + search(array, 3));
		System.out.println("array = " + search(array, 4));
		System.out.println("array = " + search(array, 5));
		System.out.println("array = " + search(array, 6));
		System.out.println("array = " + search(array, 7));
	}

	/**
	 * 我们发现循环数组存在一个性质：以数组中间点为分区，会将数组分成一个有序数组和一个循环有序数组。
	 * 
	 * @param a     数组
	 * @param value 要寻找的值
	 * @return 返回的位置，若找不到则为 -1
	 */
	public static int search(int[] array, int value) {
		return search(array, 0, array.length - 1, value);
	}
	
	private static int search(int[] array, int low, int high, int value) {
		int find = -1;
		if (low <= high) {
			int mid = low + ((high - low) >>> 1);
			if (array[mid] == value) {
				find = mid;
			} else {
				// 左边有序，右边依旧循环
				if (array[low] < array[mid]) {
					if (array[low] <= value && value <= array[mid]) {
						// 此处建议采用二分查找，当然也可以继续递归使用 search 方法
						find = search(array, low, mid - 1, value);
					} else {
						find = search(array, mid + 1, high, value);
					}
				} 
				// 右边边有序，左边依旧循环
				else {
					// 此处建议采用二分查找，当然也可以继续递归使用 search 方法
					if (array[mid] <= value && value <= array[high]) {
						find = search(array, mid + 1, high, value);
					} else {
						find = search(array, low, mid - 1, value);
					}
				}
			}
		}
		return find;
	}
		
}
